
// 1477. 找两个和为目标值且不重叠的之数组
class Solution {
public:
    int minSumOfLengths(vector<int>& nums, int target) {
        // 使用两个前缀和来实现 
        // f记录从前往后到达 i 位置时,前面子数组中和为tar的最短长度
        // g记录从后往前到达 i 位置时,后面子数组中和为tar的最短长度
        const int INF = 0x3f3f3f3f;

        int n = nums.size();
        vector<int> f(n+1,INF), g(n+1,INF);     // f记录在i之前和为target的最短子数组长度,不包含i位置  ; g记录i之后最短子数组长度,包含i位置
        unordered_map<int,int> l , r;           // 其中l记录在i之前存在的前缀和 , r记录在 n -1 -i之后存在的前缀和
        l.insert({0,-1});                       // 初始化 , 带上-1位置标记从0开始的子数组
        r.insert({0,n});                        
        int sum1 = 0 , sum2 = 0;
        for(int i = 0 ;i < n ;i++)
        {
            int j = n - 1 - i;                  // 记录从后往前的坐标
            sum1 += nums[i],sum2 += nums[j];
            f[i+1] = f[i],g[j] = g[j+1];        // 先进行赋值, 在判断能否进行比较
            if(l.count(sum1 - target)) f[i+1] = min(f[i] , i - l[sum1 - target]);
            if(r.count(sum2 - target)) g[j] = min(g[j+1]  , r[sum2 - target] - j);
            l[sum1] = i,r[sum2] = j;
        }
        
        int ret = INF;
        for(int i = 1; i < n-1 ;i++)            // 遍历每个位置向前向后找最小和
            ret = min(ret, f[i] + g[i]);
        return ret >= INF ? -1 : ret;
    }
};